//给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。 
//
// 说明： 
//你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。 
//
// 示例 1: 
//
// 输入: root = [3,1,4,null,2], k = 1
//   3
//  / \
// 1   4
//  \
//   2
//输出: 1 
//
// 示例 2: 
//
// 输入: root = [5,3,6,2,4,null,null,1], k = 3
//       5
//      / \
//     3   6
//    / \
//   2   4
//  /
// 1
//输出: 3 
//
// 进阶： 
//如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？ 
// Related Topics 树 二分查找 
// 👍 246 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：二叉搜索树中第K小的元素
public class P230KthSmallestElementInABst{
    public static void main(String[] args) {
        Solution solution = new P230KthSmallestElementInABst().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
  /*
  找第k个最小的元素
  对二叉树进行中序遍历
  * */
class Solution {
    int cnt=0;
    int res=0;
    public int kthSmallest(TreeNode root, int k) {
        /*
        List<Integer> list=new ArrayList<>();
        inorder(root,list);
        return list.get(k-1);*/
        inorder2(root,k);
        return res;
    }

    /*
    使用集合
    * */
    public void inorder(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        if(root.left!=null){
            inorder(root.left,list);
        }
        list.add(root.val);
        if(root.right!=null){
            inorder(root.right,list);
        }
    }

    /*
    不使用集合，使用两个变量记录数目和最终结果
    这块儿自己起初想的是用k--，这个是非常不建议的
    * */
    public  void inorder1(TreeNode root,int k){
        if(root==null||cnt>k){
            return;
        }

        inorder1(root.left,k);

        cnt++;
        if(cnt==k){
            res=root.val;
        }

        inorder1(root.right,k);

    }
      /*
      * 这种方法不可行 ,输出结果错误
      * */
      public  void inorder2(TreeNode root,int k){
          if(root==null||k<0){
              return;
          }

          inorder2(root.left,k);

          k--;
          if(k==0){
              res=root.val;
          }

          inorder2(root.right,k);

      }
}
//leetcode submit region end(Prohibit modification and deletion)

}
